#!/usr/bin/python
#
# exp.py - Classes to represent underlying data structures for the grammar
#     below, for the mini-compiler.
#
# Kurt Schmidt
# 8/07
#
# DESCRIPTION:
#        Just a translation of the C++ implementation by Jeremy Johnson (see
#        programext.cpp)
#
# EDITOR: cols=80, tabstop=2
#
# NOTES
#    environment:
#        a dict
#
#        Procedure calls get their own environment, can not modify enclosing env
#
#    Grammar:
#        program: stmt_list 
#        stmt_list:  stmt ';' stmt_list 
#            |   stmt  
#        stmt:  assign_stmt 
#            |  define_stmt 
#            |  if_stmt 
#            |  while_stmt 
#        assign_stmt: IDENT ASSIGNOP expr
#        define_stmt: DEFINE IDENT PROC '(' param_list ')' stmt_list END
#        if_stmt: IF expr THEN stmt_list ELSE stmt_list FI
#        while_stmt: WHILE expr DO stmt_list OD
#        param_list: IDENT ',' param_list 
#            |      IDENT 
#        expr: expr '+' term   
#            | expr '-' term   
#            | term            
#        term: term '*' factor   
#            | factor            
#        factor:     '(' expr ')'  
#            |       NUMBER 
#            |       IDENT 
#            |       funcall 
#        funcall:  IDENT '(' expr_list ')'
#        expr_list: expr ',' expr_list 
#            |      expr 
#

import sys
import copy

####  CONSTANTS   ################

    # the variable name used to store a proc's return value
returnSymbol = 'return'

tabstop = '  ' # 2 spaces

scope = 'stat'

######   CLASSES   ##################

class Expr :
	'''Virtual base class for expressions in the language'''

	def __init__( self ) :
		raise NotImplementedError('Expr: pure virtual base class.  Do not instantiate' )

	def eval( self, nt, ft ) :
		'''Given an environment and a function table, evaluates the expression,
		returns the value of the expression (an int in this grammar)'''

		raise NotImplementedError('Expr.eval: virtual method.  Must be overridden.' )

	def display( self, nt, ft, depth=0 ) :
		'For debugging.'
		raise NotImplementedError(
		'Expr.display: virtual method.  Must be overridden.' )

class Number( Expr ) :
	'''Just integers'''

	def __init__( self, v=0 ) :
		self.value = v
	def eval( self, nt, ft ) :
		return self.value

	def display( self, nt, ft, depth=0 ) :
		print "%s%i" % (tabstop*depth, self.value)

class Ident( Expr ) :
	'''Stores the symbol'''

	def __init__( self, name ) :
		self.name = name
	def eval( self, nt, ft ) :
		if(self.name in nt):
			return nt[ self.name ]
		else:
			return ft[ self.name ]

	def display( self, nt, ft, depth=0 ) :
		print "%s%s" % (tabstop*depth, self.name)


class Times( Expr ) :
	'''expression for binary multiplication'''

	def __init__( self, lhs, rhs ) :
		'''lhs, rhs are Expr's, the operands'''

		# test type here?
		# if type( lhs ) == type( Expr ) :
		self.lhs = lhs
		self.rhs = rhs

	def eval( self, nt, ft ) :
		return self.lhs.eval( nt, ft ) * self.rhs.eval( nt, ft )

	def display( self, nt, ft, depth=0 ) :
		print "%sMULT" % (tabstop*depth)
		self.lhs.display( nt, ft, depth+1 )
		self.rhs.display( nt, ft, depth+1 )
		#print "%s= %i" % (tabstop*depth, self.eval( nt, ft ))


class Plus( Expr ) :
	'''expression for binary addition'''

	def __init__( self, lhs, rhs ) :
		self.lhs = lhs
		self.rhs = rhs
	def eval( self, nt, ft ) :
		return self.lhs.eval( nt, ft ) + self.rhs.eval( nt, ft )

	def display( self, nt, ft, depth=0 ) :
		print "%sADD" % (tabstop*depth)
		self.lhs.display( nt, ft, depth+1 )
		self.rhs.display( nt, ft, depth+1 )
		#print "%s= %i" % (tabstop*depth, self.eval( nt, ft ))


class Minus( Expr ) :
	'''expression for binary subtraction'''

	def __init__( self, lhs, rhs ) :
		self.lhs = lhs
		self.rhs = rhs

	def eval( self, nt, ft ) :
		return self.lhs.eval( nt, ft ) - self.rhs.eval( nt, ft )

	def display( self, nt, ft, depth=0 ) :
		print "%sSUB" % (tabstop*depth)
		self.lhs.display( nt, ft, depth+1 )
		self.rhs.display( nt, ft, depth+1 )
		#print "%s= %i" % (tabstop*depth, self.eval( nt, ft ))


class FunCall( Expr ) :
	'''stores a function call:
	- its name, and arguments'''

	def __init__( self, name, argList ) :
		self.name = name
		self.argList = argList

	def eval( self, nt, ft ) :
		return ft[ self.name ].apply( nt, ft, self.argList )

	def display( self, nt, ft, depth=0 ) :
		print "%sFunction Call: %s, args:" % (tabstop*depth, self.name)
		for e in self.argList :
			e.display( nt, ft, depth+1 )


class Cons( Expr ) :
	'''puts element at beginning of list'''
	def __init__( self, listelement, list):
		self.listelement = listelement
		self.list = list
	def eval(self, nt, ft) :
		self.listelement = self.listelement.eval(nt,ft)
		self.list = self.list.eval(nt,ft)
		if(type(self.list) is int):
			sys.exit("Cons second argument must be of type list")
		c = []
		for i in range(0,len(self.list)):
			c.append(self.list[i])
		c.insert(0,self.listelement)
		return c


class Car( Expr ) :
	'''Removes first element in the list'''
	def __init__(self, list):
		self.list = list     
	def eval(self, nt, ft) :
		rList = self.list.eval(nt,ft)
		if(type(rList) is int):
			sys.exit("Car argument must be of type list")
		if(len(rList) < 1):
			sys.exit("Car argument must be a non-null list")
		return rList[0]

class Cdr ( Expr ) :
	'''Returns all but first element'''
	def __init__(self, list):
		self.list = list
	def eval(self, nt, ft) :
		rList = self.list.eval(nt,ft)
		if(type(rList) is int):
			sys.exit("Cdr argument must be of type list")
		c = []
		for i in range(1,len(rList)):
			c.append(rList[i])
		return c

class Nullp ( Expr ) :
	'''Returns 1 if L is null, 0 otherwise'''
	def __init__(self, list):
		self.list = list
	def eval(self, nt, ft) :
		rList = self.list.eval(nt,ft)
		if(type(rList) is int):
			sys.exit("Nullp argument must be of type list")
		if(len(rList)==0) :
			return 1
		else :
			return 0
class Intp ( Expr ) :
	'''Returns 1 if E is an integer, 0 otherwise'''
	def __init__(self, e) :
		self.e = e
	def eval(self, nt, ft) :
		rE = self.e.eval(nt,ft)
		if(type(rE) is int):
			return 1
		else :
			return 0

class Listp ( Expr ) :
	'''Returns 1 if E is a list, 0 otherwise'''
	def __init__(self, e) :
		self.e = e
	def eval(self, nt, ft) :
		rE = self.e.eval(nt,ft)
		if(type(rE) is int):
			return 0
		else :
			return 1
class Concat ( Expr ) :
	'''Concatenates two lists'''
	def __init__(self, l1, l2):
		self.l1 = l1
		self.l2 = l2
	def eval(self, nt, ft) :
		rL1 = self.l1.eval(nt,ft)
		rL2 = self.l2.eval(nt,ft)
		if(type(rL1) is int or type(rL2) is int):
			sys.exit("List concatenation requires two lists")
		c = []
		for i in range(0,len(rL1)) :
			c.append(rL1[i])
		for i in range(0,len(rL2)) :
			c.append(rL2[i])
		return c


class List( Expr ) :
	'''List'''
	def __init__(self, seq=[]) :
		self.seq = seq
	def insert(self, listelement) :
		self.seq.insert(listelement)      

	def eval(self, nt, ft) :
		return self.seq.eval(nt,ft)

	def display( self, nt, ft, depth=0):
		print "%sList[" % (tabstop*depth)
		self.seq.display(nt,ft,depth+1)
		print "%s]" % (tabstop*depth)
	def size(self) :
		return len(self.seq)

class Sequence ( Expr ) :
	'''Sequence'''
	def __init__(self):
		self.seq = []
	def insert(self, listelement):
		self.seq.insert(0, listelement)  
	def eval(self, nt, ft) :
		seqValue = []
		for s in self.seq :
			seqValue.append(s.eval(nt,ft))
		return seqValue
	def display(self, nt, ft, depth=0):
		print "%sSeqence " % (tabstop*depth)
		for s in self.seq :
			s.display(nt,ft,depth+1)
	def size(self) :
		return len(self.seq)

class Listelement( Expr ) :
	'''List Element'''
	def __init__(self, element) :
		self.element = element
	def eval(self, nt, ft) :
		return self.element.eval(nt,ft)
	def display(self, nt,ft, depth=0):
		print "%s" % (tabstop*depth)
		self.element.display(nt,ft,depth+1)


#-------------------------------------------------------

class Stmt :
	'''Virtual base class for statements in the language'''
	def __init__( self ) :
		raise NotImplementedError(
		'Stmt: pure virtual base class.  Do not instantiate' )

	def eval( self, nt, ft ) :
		'''Given an environment and a function table, evaluates the expression,
		returns the value of the expression (an int in this grammar)'''
		raise NotImplementedError(
		'Stmt.eval: virtual method.  Must be overridden.' )

	def display( self, nt, ft, depth=0 ) :
		'For debugging.'
		raise NotImplementedError(
		'Stmt.display: virtual method.  Must be overridden.' )


class AssignStmt( Stmt ) :
	'''adds/modifies symbol in the current context'''

	def __init__( self, name, rhs ) :
		'''stores the symbol for the l-val, and the expressions which is the
		rhs'''
		self.name = name
		self.rhs = rhs

	def eval( self, nt, ft ) :
		if(isinstance(self.rhs, Proc)):
			newRhs = copy.deepcopy(self.rhs)
			ft[ self.name ] = newRhs
		else:
			evalVal = self.rhs.eval( nt, ft )
			if(isinstance(evalVal, Proc)):
				ft[ self.name ] = evalVal
			else:
				nt[ self.name ] = evalVal
#			nt[self.name] = self.rhs.eval( nt, ft)
	def display( self, nt, ft, depth=0 ) :
		print "%sAssign: %s :=" % (tabstop*depth, self.name)
		self.rhs.display( nt, ft, depth+1 )

'''
class DefineStmt( Stmt ) :
#	Binds a proc object to a name

	def __init__( self, name, proc ) :
		print('defining: '+str(name))
		self.name = name
		self.proc = proc

	def eval( self, nt, ft ) :
		ft[ self.name ] = self.proc

	def display( self, nt, ft, depth=0 ) :
		print "%sDEFINE %s :" % (tabstop*depth, self.name)
		self.proc.display( nt, ft, depth+1 )
'''

class IfStmt( Stmt ) :

	def __init__( self, cond, tBody, fBody ) :
		'''expects:
		cond - expression (integer)
		tBody - StmtList
		fBody - StmtList'''

		self.cond = cond
		self.tBody = tBody
		self.fBody = fBody

	def eval( self, nt, ft ) :
		if self.cond.eval( nt, ft ) > 0 :
			self.tBody.eval( nt, ft )
		else :
			self.fBody.eval( nt, ft )

	def display( self, nt, ft, depth=0 ) :
		print "%sIF" % (tabstop*depth)
		self.cond.display( nt, ft, depth+1 )
		print "%sTHEN" % (tabstop*depth)
		self.tBody.display( nt, ft, depth+1 )
		print "%sELSE" % (tabstop*depth)
		self.fBody.display( nt, ft, depth+1 )


class WhileStmt( Stmt ) :

	def __init__( self, cond, body ) :
		self.cond = cond
		self.body = body

	def eval( self, nt, ft ) :
		while self.cond.eval( nt, ft ) > 0 :
			self.body.eval( nt, ft )

	def display( self, nt, ft, depth=0 ) :
		print "%sWHILE" % (tabstop*depth)
		self.cond.display( nt, ft, depth+1 )
		print "%sDO" % (tabstop*depth)
		self.body.display( nt, ft, depth+1 )

class WhileNotStmt( Stmt ) :
	
	def __init__( self, cond, body ) :
		self.cond = cond
		self.body = body
	
	def eval( self, nt, ft) :
		while self.cond.eval( nt, ft ) < 1:
			self.body.eval(nt, ft)

	def display( self, nt, ft, depth=0) :
		print "%sWHILE NOT" % (tabstop*depth)
		self.cond.display(nt,ft,depth+1)
		print "%sDO" % (tabstop*depth)
		self.body.display(nt,ft,depth+1)

#-------------------------------------------------------

class StmtList :
	'''builds/stores a list of Stmts'''

	def __init__( self ) :
		self.sl = []

	def insert( self, stmt ) :
		self.sl.insert( 0, stmt )

	def eval( self, nt, ft ) :
		for s in self.sl :
			s.eval( nt, ft )

	def display( self, nt, ft, depth=0 ) :
		print "%sSTMT LIST" % (tabstop*depth)
		for s in self.sl :
			s.display( nt, ft, depth+1 )


class Proc :
	'''stores a procedure (formal params, and the body)

    Note that, while each function gets its own environment, we decided not to
    allow side-effects, so, no access to any outer contexts.  Thus, nesting
    functions is legal, but no different than defining them all in the global
    environment.  Further, all calls are handled the same way, regardless of
    the calling environment (after the actual args are evaluated); the proc
    doesn't need/want/get an outside environment.'''


	def __init__( self, paramList, body ) :
		'''expects a list of formal parameters (variables, as strings), and a
		StmtList'''
		self.nt = {}
		self.ft = {}
		
		self.parList = paramList
		self.body = body

	def apply( self, nt, ft, args ) :

		# sanity check, # of args
		if len( args ) is not len( self.parList ) :
			print "Param count does not match:"
			sys.exit( 1 )

		## Copy parameters from defining environment, and add parameters
		## to bindings
## Save for Dyn
		if(scope=='dyn'):
			self.nt = copy.deepcopy(nt)
			self.ft = copy.deepcopy(ft)
		for i in range( len( args )) :
			evaluated = args[i].eval(nt,ft)
			if(isinstance(evaluated, Proc)):
				self.ft[ self.parList[i] ] = evaluated
			else:
				self.nt[ self.parList[i] ] = evaluated

		# evaluate the function body using the new name table and the old (only)
		# function table.  Note that the proc's return value is stored as
		# 'return in its nametable
	
		self.body.eval( self.nt, self.ft )
		if self.nt.has_key( returnSymbol ) :
			return self.nt[ returnSymbol ]
		elif self.ft.has_key( returnSymbol ):
			if scope=='stat':
				for key in self.nt.iterkeys():
					self.ft[ returnSymbol ].nt[key] = self.nt[key]
				for key in self.ft.iterkeys():
					self.ft[ returnSymbol ].ft[key] = self.ft[key]
			
			return self.ft[ returnSymbol ]
	
		else :
			print "Error:  no return value"
			sys.exit( 2 )

	def display( self, nt, ft, depth=0 ) :
		print "%sPROC %s :" % (tabstop*depth, str(self.parList))
		self.body.display( nt, ft, depth+1 )


class Program :

	def __init__( self, stmtList, scopeType ) :
		self.stmtList = stmtList
		self.nameTable = {}
		self.funcTable = {}
		print 'setting scope to '+scopeType
		scope = scopeType

	def eval( self ) :
		self.stmtList.eval( self.nameTable, self.funcTable )

	def dump( self ) :
		print "Dump of Symbol Table"
		print "Name Table"
		for k in self.nameTable :
			print "  %s -> %s " % ( str(k), str(self.nameTable[k]) )
		print "Function Table"
		for k in self.funcTable :
			print "  %s" % str(k)

	def display( self, depth=0 ) :
		print "%sPROGRAM :" % (tabstop*depth)
		self.stmtList.display( self.nameTable, self.funcTable )


